package com.lagou.task2;

/**
 * 给定一个链表，判断链表中是否有环。存在环返回 true ，否则返回 false
 *
 * 思路：
 * 该题可以理解为“追击相遇”问题，如果存在环，跑得快的一定能追上跑得慢的。
 * 比如：一快一慢两个运动员，如果在直道赛跑，不存在追击相遇问题；如果是在环道赛跑，快的绕了一
 * 圈肯定可以追上慢的。
 *
 * 解法：
 * 1. 定义快慢两个指针：
 * slow=head; fast=head.next;
 * 2. 遍历链表：
 * 快指针步长为2：fast=fast.next.next; 慢指针步长为1：slow=slow.next;
 * 3. 当且仅当快慢指针重合(slow==fast)，有环，返回true
 * 4. 快指针为null，或其next指向null，没有环，返回false，操作结束
 */
public class RingList {
    public static boolean isRing(Node head){
        if(head==null) return false;
        //定义快慢指针
        Node slow=head; //慢指针
        Node fast=head.next; //快指针
        while(fast!=null&&fast.next!=null){
            //有环
            if(slow==fast){
                return true;
            }

            fast=fast.next.next;// 快指针步长为2
            slow=slow.next;//慢指针步长为1
        }
        return false;
    }
    public static void main(String[] args) {
        Node n1=new Node(1,"张飞");
        Node n2=new Node(2,"关羽");
        Node n3=new Node(3,"赵云");
        Node n4=new Node(4,"黄忠");
        Node n5=new Node(5,"马超");
        n1.next=n2;
        n2.next=n3;
        n3.next=n4;
        n4.next=n5;
        //n5.next=n1;
        System.out.println(isRing(n1));
    }
}


